#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define X_SIZE 10

using namespace std;

void bfs(int array[X_SIZE][X_SIZE],struct point pointArr[X_SIZE],int start,int point_size);

struct point 
{
	int visit;
	int d;
	int pre;
};

int main()
{
	int i,x,y,point_size,line_size,start,array[X_SIZE][X_SIZE];
	memset(array,0,sizeof(array));
	scanf("%d %d %d",&point_size,&line_size,&start);
	for(int i = 0;i < line_size;i++) 
	{
		scanf("%d %d",&x,&y);
		array[x][y] = 1;
		array[y][x] = 1;
	}
	struct point pointArr[X_SIZE];
	for(int i = 0;i < X_SIZE;i++)
	{
		pointArr[i].visit = 0;
	}
	bfs(array,pointArr,start,point_size);
	for(int i = 0;i < point_size;i++)
	{
		printf("%d:%d\n",i,pointArr[i].d);
	}

	return 0;
}

void bfs(int array[X_SIZE][X_SIZE],struct point pointArr[X_SIZE],int start,int point_size)
{
	pointArr[start].visit = 1;
	pointArr[start].d = 0;
	pointArr[start].pre = start;
	queue<int> pointQue;
	pointQue.push(start);
	while(!pointQue.empty())
	{
		int u = pointQue.front();
		for(int i = 0;i < point_size;i++)
		{
			if(array[u][i] == 1 && pointArr[i].visit == 0)
			{
				pointArr[i].visit = 1;
				pointArr[i].d = pointArr[u].d + 1;
				pointArr[i].pre = u;
				pointQue.push(i);
			}
		}
		pointArr[u].visit = 2;
		pointQue.pop();
	}
}
